// https://leetcode.cn/problems/binary-search/description/

// 算法思路总结：
// 1. 二分查找模板：左开右开区间初始化
// 2. 循环条件维持 l+1 != r 保证区间有效性
// 3. 中间位置计算使用位运算优化
// 4. 根据比较结果收缩左右边界
// 5. 时间复杂度：O(log n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int search(vector<int>& nums, int target) 
    {
        int l = -1, r = nums.size();

        while (l + 1 != r)
        {
            int mid = (l + r) >> 1;
            if (nums[mid] < target)
            {
                l = mid;
            }
            else 
            {
                r = mid;
            }
        }

        if (r == nums.size() || nums[r] != target)
        {
            return -1;
        }

        return r;
    }
};

int main()
{
    vector<int> nums1 = {-1,0,3,5,9,12}, nums2 = {-1,0,3,5,9,12};
    int target1 = 9, target2 = 2;

    Solution sol;

    cout << sol.search(nums1, target1) << endl;
    cout << sol.search(nums2, target2) << endl;

    return 0;
}